Balanced binary trees are a useful data structure for maintaining
large sets of ordered objects or sets of associations whose keys are
ordered. MIT Scheme has an comprehensive implementation of
weight-balanced binary trees which has several advantages over the
other data structures for large aggregates:
* In addition to the usual element-level operations like insertion,
deletion and lookup, there is a full complement of collection-level
operations, like set intersection, set union and subset test, all
of which are implemented with good orders of growth in time and
space. This makes weight balanced trees ideal for rapid
prototyping of functionally derived specifications.
* An element in a tree may be indexed by its position under the
ordering of the keys, and the ordinal position of an element may
be determined, both with reasonable efficiency.
* Operations to find and remove minimum element make weight balanced
trees simple to use for priority queues.
* The implementation is *functional* rather than *imperative*. This
means that operations like `inserting' an association in a tree do
not destroy the old tree, in much the same way that `(+ 1 x)'
modifies neither the constant 1 nor the value bound to `x'. The
trees are referentially transparent thus the programmer need not
worry about copying the trees. Referential transparency allows
space efficiency to be achieved by sharing subtrees.
These features make weight-balanced trees suitable for a wide range of
applications, especially those that require large numbers of sets or
discrete maps. Applications that have a few global databases and/or
concentrate on element-level operations like insertion and lookup are
probably better off using hash-tables or red-black trees.
The *size* of a tree is the number of associations that it contains.
Weight balanced binary trees are balanced to keep the sizes of the
subtrees of each node within a constant factor of each other. This
ensures logarithmic times for single-path operations (like lookup and
insertion). A weight balanced tree takes space that is proportional to
the number of associations in the tree. For the current
implementation, the constant of proportionality is six words per
association.
Weight balanced trees can be used as an implementation for either
discrete sets or discrete maps (associations). Sets are implemented by
ignoring the datum that is associated with the key. Under this scheme
if an associations exists in the tree this indicates that the key of the
association is a member of the set. Typically a value such as `()',
`#t' or `#f' is associated with the key.
Many operations can be viewed as computing a result that, depending on
whether the tree arguments are thought of as sets or maps, is known by
two different names. An example is `wt-tree/member?', which, when
regarding the tree argument as a set, computes the set membership
operation, but, when regarding the tree as a discrete map,
`wt-tree/member?' is the predicate testing if the map is defined at an
element in its domain. Most names in this package have been chosen
based on interpreting the trees as sets, hence the name
`wt-tree/member?' rather than `wt-tree/defined-at?'.
The weight balanced tree implementation is a run-time-loadable option.
To use weight balanced trees, execute
(load-option 'wt-tree)
once before calling any of the procedures defined here.
* Menu:
* Construction of Weight-Balanced Trees::
* Basic Operations on Weight-Balanced Trees::
* Advanced Operations on Weight-Balanced Trees::
* Indexing Operations on Weight-Balanced Trees::
File: slib.info, Node: Construction of Weight-Balanced Trees, Next: Basic Operations on Weight-Balanced Trees, Prev: Weight-Balanced Trees, Up: Weight-Balanced Trees
Construction of Weight-Balanced Trees
-------------------------------------
Binary trees require there to be a total order on the keys used to
arrange the elements in the tree. Weight balanced trees are organized
by *types*, where the type is an object encapsulating the ordering
relation. Creating a tree is a two-stage process. First a tree type
must be created from the predicate which gives the ordering. The tree
type is then used for making trees, either empty or singleton trees or
trees from other aggregate structures like association lists. Once
created, a tree `knows' its type and the type is used to test
compatibility between trees in operations taking two trees. Usually a
small number of tree types are created at the beginning of a program and
used many times throughout the program's execution.
- procedure+: make-wt-tree-type KEY<?
This procedure creates and returns a new tree type based on the
ordering predicate KEY<?. KEY<? must be a total ordering, having
the property that for all key values `a', `b' and `c':
(key<? a a) => #f
(and (key<? a b) (key<? b a)) => #f
(if (and (key<? a b) (key<? b c))
(key<? a c)
#t) => #t
Two key values are assumed to be equal if neither is less than the
other by KEY<?.
Each call to `make-wt-tree-type' returns a distinct value, and
trees are only compatible if their tree types are `eq?'. A
consequence is that trees that are intended to be used in binary
tree operations must all be created with a tree type originating
from the same call to `make-wt-tree-type'.
- variable+: number-wt-type
A standard tree type for trees with numeric keys. `Number-wt-type'
could have been defined by
(define number-wt-type (make-wt-tree-type <))
- variable+: string-wt-type
A standard tree type for trees with string keys. `String-wt-type'
This procedure creates and returns a newly allocated weight
balanced tree. The tree is empty, i.e. it contains no
associations. WT-TREE-TYPE is a weight balanced tree type
obtained by calling `make-wt-tree-type'; the returned tree has
this type.
- procedure+: singleton-wt-tree WT-TREE-TYPE KEY DATUM
This procedure creates and returns a newly allocated weight
balanced tree. The tree contains a single association, that of
DATUM with KEY. WT-TREE-TYPE is a weight balanced tree type
obtained by calling `make-wt-tree-type'; the returned tree has
this type.
- procedure+: alist->wt-tree TREE-TYPE ALIST
Returns a newly allocated weight-balanced tree that contains the
same associations as ALIST. This procedure is equivalent to:
(lambda (type alist)
(let ((tree (make-wt-tree type)))
(for-each (lambda (association)
(wt-tree/add! tree
(car association)
(cdr association)))
alist)
tree))
File: slib.info, Node: Basic Operations on Weight-Balanced Trees, Next: Advanced Operations on Weight-Balanced Trees, Prev: Construction of Weight-Balanced Trees, Up: Weight-Balanced Trees
Basic Operations on Weight-Balanced Trees
-----------------------------------------
This section describes the basic tree operations on weight balanced
trees. These operations are the usual tree operations for insertion,
deletion and lookup, some predicates and a procedure for determining the
number of associations in a tree.
- procedure+: wt-tree? OBJECT
Returns `#t' if OBJECT is a weight-balanced tree, otherwise
returns `#f'.
- procedure+: wt-tree/empty? WT-TREE
Returns `#t' if WT-TREE contains no associations, otherwise
returns `#f'.
- procedure+: wt-tree/size WT-TREE
Returns the number of associations in WT-TREE, an exact
non-negative integer. This operation takes constant time.
- procedure+: wt-tree/add WT-TREE KEY DATUM
Returns a new tree containing all the associations in WT-TREE and
the association of DATUM with KEY. If WT-TREE already had an
association for KEY, the new association overrides the old. The
average and worst-case times required by this operation are
proportional to the logarithm of the number of associations in
WT-TREE.
- procedure+: wt-tree/add! WT-TREE KEY DATUM
Associates DATUM with KEY in WT-TREE and returns an unspecified
value. If WT-TREE already has an association for KEY, that
association is replaced. The average and worst-case times
required by this operation are proportional to the logarithm of
the number of associations in WT-TREE.
- procedure+: wt-tree/member? KEY WT-TREE
Returns `#t' if WT-TREE contains an association for KEY, otherwise
returns `#f'. The average and worst-case times required by this
operation are proportional to the logarithm of the number of
associations in WT-TREE.
- procedure+: wt-tree/lookup WT-TREE KEY DEFAULT
Returns the datum associated with KEY in WT-TREE. If WT-TREE
doesn't contain an association for KEY, DEFAULT is returned. The
average and worst-case times required by this operation are
proportional to the logarithm of the number of associations in
WT-TREE.
- procedure+: wt-tree/delete WT-TREE KEY
Returns a new tree containing all the associations in WT-TREE,
except that if WT-TREE contains an association for KEY, it is
removed from the result. The average and worst-case times required
by this operation are proportional to the logarithm of the number
of associations in WT-TREE.
- procedure+: wt-tree/delete! WT-TREE KEY
If WT-TREE contains an association for KEY the association is
removed. Returns an unspecified value. The average and worst-case
times required by this operation are proportional to the logarithm
of the number of associations in WT-TREE.
File: slib.info, Node: Advanced Operations on Weight-Balanced Trees, Next: Indexing Operations on Weight-Balanced Trees, Prev: Basic Operations on Weight-Balanced Trees, Up: Weight-Balanced Trees
Advanced Operations on Weight-Balanced Trees
--------------------------------------------
In the following the *size* of a tree is the number of associations
that the tree contains, and a *smaller* tree contains fewer
associations.
- procedure+: wt-tree/split< WT-TREE BOUND
Returns a new tree containing all and only the associations in
WT-TREE which have a key that is less than BOUND in the ordering
relation of the tree type of WT-TREE. The average and worst-case
times required by this operation are proportional to the logarithm
of the size of WT-TREE.
- procedure+: wt-tree/split> WT-TREE BOUND
Returns a new tree containing all and only the associations in
WT-TREE which have a key that is greater than BOUND in the
ordering relation of the tree type of WT-TREE. The average and
worst-case times required by this operation are proportional to the
logarithm of size of WT-TREE.
- procedure+: wt-tree/union WT-TREE-1 WT-TREE-2
Returns a new tree containing all the associations from both trees.
This operation is asymmetric: when both trees have an association
for the same key, the returned tree associates the datum from
WT-TREE-2 with the key. Thus if the trees are viewed as discrete
maps then `wt-tree/union' computes the map override of WT-TREE-1 by
WT-TREE-2. If the trees are viewed as sets the result is the set
union of the arguments. The worst-case time required by this
operation is proportional to the sum of the sizes of both trees.
If the minimum key of one tree is greater than the maximum key of
the other tree then the time required is at worst proportional to
